import java.util.*;
public class FindClosest {
    public static int findClosest(String[] words, String word1, String word2) {
       Map<String, List<Integer>> cnt = new HashMap<>();
       for(int i = 0; i < words.length; i++) {
           String word = words[i];
           cnt.computeIfAbsent(word, k-> new ArrayList<>()).add(i);
       }
      List<Integer> index1 = cnt.get(word1);
      List<Integer> index2 = cnt.get(word2);
      // Use two-pointer technique to find minimum distance
      int i = 0, j = 0;
      int minDistance = Integer.MAX_VALUE;
      
      while (i < index1.size() && j < index2.size()) {
          int distance = Math.abs(index1.get(i) - index2.get(j));
          minDistance = Math.min(minDistance, distance);
          
          // Move the pointer pointing to the smaller index
          if (index1.get(i) < index2.get(j)) {
              i++;
          } else {
              j++;
          }
          
          // Early exit if we find distance 0 (can't get closer)
          if (minDistance == 0) {
              break;
          }
      }
       return minDistance;
    }
    class Solution {
    public int findClosest2(String[] words, String word1, String word2) {
        int n = words.length;
        String w = "";
        int min = Integer.MAX_VALUE / 2;
        int last = Integer.MIN_VALUE / 2;
        for (int i = 0; i < n; i++) {
            if (words[i].equals(word1) || words[i].equals(word2)) {
                if (!words[i].equals(w)) {
                    min = Math.min(min, i - last);
                    w = words[i];
                }
                last = i;
            }
            if (min == 1) {
                break;
            }
        }
        return min;
    }
}
    public static void main(String[] args) {
        String[] points = new String[]{"I","am","a","student","from","a","university","in","a","city"};
        String word1 = "a";
        String word2 = "student";
        int res = findClosest(points, word1, word2);
        System.out.println(res);
    }
}


// 有个内含单词的超大文本文件，给定任意两个不同的单词，找出在这个文件中这两个单词的最短距离(相隔单词数)。如果寻找过程在这个文件中会重复多次，而每次寻找的单词不同，你能对此优化吗?

// 示例：

// 输入：words = ["I","am","a","student","from","a","university","in","a","city"], word1 = "a", word2 = "student"
// 输出：1
// 提示：

// words.length <= 100000

